The present invention is directed to the field of secure communications. It is more particularly related to secure digital signature schemes.
With today""s exponential growth in the volume of electronic communications, there is a need for cryptographic tools that offer high security as well as high efficiency. Communication networks todays must support exchange of sensitive information (e.g., medical files), remote access of data, electronic commerce, and a variety of other tasks. At the very least, the network is expected to ensure integrity and authenticity of data, and often also confidentiality.
When a message is transmitted from one party to another, the receiving party may desire to determine whether the message has been altered in transit. Furthermore, the receiving party may which to be certain of the origin of the message. Traditionally, written data has been authenticated by appending the hand-written signature of the appropriate individual to the data. In the realm of electronic communication, methods for authenticating data proceed in a similar fashion, except that the hand-written signature is replaced with a digital signature. The digital signature is computed by the signer based on the message being signed.
The digital signature should have the properties that anyone can verify that a signature is the valid signature of the signer for the associated message, and that only the signer is able to generate the signature. Hence, digital signature methods may also be used to prove to a third party that the message was signed by the actual signer, thus providing non repudiation.
A typical system wherein a sender is using a digital signature scheme to authenticate messages that it sends to a receiver is depicted in FIG. 1. In this figure, a dashed line separates the operations of a sender 100 on the left from the operation of a receiver 110 on the right. In a preliminary operation, the sender 100 uses a key generation process 101 to generate a public key 102 and a secret key 103. The public key 102 is made available to the receiver 110 before any message is sent using some mechanism. Mechanisms to supply the public key to the receiver 110 are well known in the art, and are not discussed in this patent. The secret key 103 is kept secret by the sender 100.
To authenticate a message 104, the sender 100 uses a signing process 105, giving it as input the message 104 and the secret key 103. The output of the signing process 105 is a signature 106 on the message 104. The sender 100 uses conventional communication equipment to transmit both the message 104 and the signature 106 to the receiver 110. The receiver 110 uses a verification process 107, giving it as input the public key 102, the message 104 and the signature 106. The output of the verification process 107 signifies that the signature is valid 108, or that an invalid signature has been detected.
Several digital signature methods are known in the art. The most popular method today for computing digital signatures in the RSA scheme. The strongest notion of security of digital signatures is called existential unforgeability under an adaptive chosen message attack. It requires that forging a signature of an arbitrary message without knowing the secret key is not feasible, even if an attacker receives several signatures on messages of its choice. Construction of efficient signature schemes for which it is possible to prove existential unforgeability under an adaptive chosen message attack is a long standing challenge. Prior to the present invention, the only schemes for which such proofs are known were based on xe2x80x9csignature treesxe2x80x9d, and were not very efficient. Another drawback of these prior schemes is their stateful nature, i.e. the signer has to store some information from previously signed messages.
Another line of research concentrates on hash-and-sign schemes, wherein the message to be signed is hashed using a cryptographic hash function. The result is signed using a standard signature scheme such as RSA. The current standard for RSA signatures is based on the hash-and-sign approach. Although hash-and-sign schemes are very efficient, they only enjoy a heuristic level of security. The only known security proofs for hash-and-sign schemes are carried out in a model wherein the hash function is assumed to be an xe2x80x9cidealxe2x80x9d one. Specifically, in these proofs the hash function is replaced by a random oracle.
It is thus an object of the present invention to provide a digital signature scheme that can be proven secure without using the random-oracle heuristic. Instead, the security proof is based on well-defined and constructable properties that are required from the hash function in use.
Another object of the invention is to provide a signature scheme which is efficient. Specifically, it should follow the hash-and-sign paradigm, by which a message is first hashed using a cryptographic hash function, and then signed using a few simple algebraic operations.
Yet another object of the invention is to provide a signature scheme in which the signer does not need to keep any state (other than the secret key) for the purpose of generating signatures.
These and other objects are provided in a digital signature scheme wherein the signature of a message relative to a public key is computed by means of a secret key. Other objects and a better understanding of the invention may be realized by referring to the Detailed Description.